<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>2.1.-Spreadsort</title>
<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../index.html" title="Boost.Sort">
<link rel="up" href="../single_thread.html" title="2.- Single Thread Algorithms">
<link rel="prev" href="../single_thread.html" title="2.- Single Thread Algorithms">
<link rel="next" href="spreadsort/sort_hpp.html" title="Spreadsort">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="../single_thread.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../single_thread.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="spreadsort/sort_hpp.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="sort.single_thread.spreadsort"></a><a class="link" href="spreadsort.html" title="2.1.-Spreadsort">2.1.-Spreadsort</a>
</h3></div></div></div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="sort.single_thread.spreadsort.overview"></a><a class="link" href="spreadsort.html#sort.single_thread.spreadsort.overview" title="Overview">Overview</a>
</h4></div></div></div>
<div class="section">
<div class="titlepage"><div><div><h5 class="title">
<a name="sort.single_thread.spreadsort.overview.intro"></a><a class="link" href="spreadsort.html#sort.single_thread.spreadsort.overview.intro" title="Introduction">Introduction</a>
</h5></div></div></div>
<p>
            Spreadsort combines generic implementations of multiple high-speed sorting
            algorithms that outperform those in the C++ standard in both average
            and worst case performance when there are over 1000 elements in the list
            to sort.
          </p>
<p>
            They fall back to <a href="http://www.cplusplus.com/reference/algorithm/sort/" target="_top">STL
            std::sort</a> on small data sets.
          </p>
<div class="warning"><table border="0" summary="Warning">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Warning]" src="../../../../../../doc/src/images/warning.png"></td>
<th align="left">Warning</th>
</tr>
<tr><td align="left" valign="top"><p>
              These algorithms all only work on <a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/" target="_top">random
              access iterators</a>.
            </p></td></tr>
</table></div>
<p>
            They are hybrids using both radix and comparison-based sorting, specialized
            to sorting common data types, such as integers, floats, and strings.
          </p>
<p>
            These algorithms are encoded in a generic fashion and accept functors,
            enabling them to sort any object that can be processed like these basic
            data types. In the case of <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/string_sort_idm2523.html" title="Function template string_sort">string_sort</a></code></code>,
            this includes anything with a defined strict-weak-ordering that <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
            can sort, but writing efficient functors for some complex key types may
            not be worth the additional effort relative to just using <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>,
            depending on how important speed is to your application. Sample usages
            are available in the example directory.
          </p>
<p>
            Unlike many radix-based algorithms, the underlying <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/spreadsort_idm2302.html" title="Function template spreadsort">spreadsort</a></code></code>
            algorithm is designed around <span class="bold"><strong>worst-case performance</strong></span>.
            It performs better on chunky data (where it is not widely distributed),
            so that on real data it can perform substantially better than on random
            data. Conceptually, <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/spreadsort_idm2302.html" title="Function template spreadsort">spreadsort</a></code></code>
            can sort any data for which an absolute ordering can be determined, and
            <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/string_sort_idm2523.html" title="Function template string_sort">string_sort</a></code></code>
            is sufficiently flexible that this should be possible.
          </p>
<p>
            Situations where <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/spreadsort_idm2302.html" title="Function template spreadsort">spreadsort</a></code></code>
            is fastest relative to <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>:
          </p>
<div class="orderedlist"><ol class="orderedlist" type="1">
<li class="listitem">
                Large number of elements to sort (<span class="emphasis"><em>N</em></span> &gt;= 10000).
              </li>
<li class="listitem">
                Slow comparison function (such as floating-point numbers on x86 processors
                or strings).
              </li>
<li class="listitem">
                Large data elements (such as key + data sorted on a key).
              </li>
<li class="listitem">
                Completely sorted data when <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/spreadsort_idm2302.html" title="Function template spreadsort">spreadsort</a></code></code>
                has an optimization to quit early in this case.
              </li>
</ol></div>
<p>
            Situations where <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/spreadsort_idm2302.html" title="Function template spreadsort">spreadsort</a></code></code>
            is slower than <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>:
          </p>
<div class="orderedlist"><ol class="orderedlist" type="1">
<li class="listitem">
                Data sorted in reverse order. Both <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
                and <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/spreadsort_idm2302.html" title="Function template spreadsort">spreadsort</a></code></code>
                are faster on reverse-ordered data than randomized data, but <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
                speeds up more in this special case.
              </li>
<li class="listitem">
                Very small amounts of data (&lt; 1000 elements). For this reason
                there is a fallback in <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/spreadsort_idm2302.html" title="Function template spreadsort">spreadsort</a></code></code>
                to <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
                if the input size is less than 1000, so performance is identical
                for small amounts of data in practice.
              </li>
</ol></div>
<p>
            These functions are defined in <code class="computeroutput">namespace boost::sort::spreadsort</code>.
          </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h5 class="title">
<a name="sort.single_thread.spreadsort.overview.overloading"></a><a class="link" href="spreadsort.html#sort.single_thread.spreadsort.overview.overloading" title="Overloading">Overloading</a>
</h5></div></div></div>
<div class="tip"><table border="0" summary="Tip">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Tip]" src="../../../../../../doc/src/images/tip.png"></td>
<th align="left">Tip</th>
</tr>
<tr><td align="left" valign="top"><p>
              In the Boost.Sort C++ Reference section, click on the appropriate overload,
              for example <code class="computeroutput">float_sort(RandomAccessIter, RandomAccessIter, Right_shift,
              Compare);</code> to get full details of that overload.
            </p></td></tr>
</table></div>
<p>
            Each of <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/integer_sort_idm1895.html" title="Function template integer_sort">integer_sort</a></code></code>,
            <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/float_sort_idm1775.html" title="Function template float_sort">float_sort</a></code></code>,
            and <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/string_sort_idm2523.html" title="Function template string_sort">string_sort</a></code></code>
            have 3 main versions: The base version, which takes a first iterator
            and a last iterator, just like <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>:
          </p>
<pre class="programlisting">integer_sort(array.begin(), array.end());
float_sort(array.begin(), array.end());
string_sort(array.begin(), array.end());
</pre>
<p>
            The version with an overridden shift functor, providing flexibility in
            case the <code class="computeroutput">operator&gt;&gt;</code> already does something other than
            a bitshift. The rightshift functor takes two args, first the data type,
            and second a natural number of bits to shift right.
          </p>
<p>
            For <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/string_sort_idm2523.html" title="Function template string_sort">string_sort</a></code></code>
            this variant is slightly different; it needs a bracket functor equivalent
            to <code class="computeroutput">operator</code>[], taking a number corresponding to the character
            offset, along with a second <code class="computeroutput">getlength</code> functor to get the
            length of the string in characters. In all cases, this operator must
            return an integer type that compares with the <code class="computeroutput">operator&lt;</code>
            to provide the intended order (integers can be negated to reverse their
            order).
          </p>
<p>
            In other words (aside from negative floats, which are inverted as ints):
          </p>
<pre class="programlisting">rightshift(A, n) &lt; rightshift(B, n) -&gt; A &lt; B
A &lt; B -&gt; rightshift(A, 0) &lt; rightshift(B, 0)
</pre>
<pre class="programlisting"><span class="identifier">integer_sort</span><span class="special">(</span><span class="identifier">array</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">array</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="identifier">rightshift</span><span class="special">());</span>
</pre>
<pre class="programlisting"><span class="identifier">string_sort</span><span class="special">(</span><span class="identifier">array</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">array</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="identifier">bracket</span><span class="special">(),</span> <span class="identifier">getsize</span><span class="special">());</span>
</pre>
<p>
            See <a href="../../../../example/rightshiftsample.cpp" target="_top">rightshiftsample.cpp</a>
            for a working example of integer sorting with a rightshift functor.
          </p>
<p>
            And a version with a comparison functor for maximum flexibility. This
            functor must provide the same sorting order as the integers returned
            by the rightshift (aside from negative floats):
          </p>
<pre class="programlisting">rightshift(A, n) &lt; rightshift(B, n) -&gt; compare(A, B)
compare(A, B) -&gt; rightshift(A, 0) &lt; rightshift(B, 0)
</pre>
<pre class="programlisting"><span class="identifier">integer_sort</span><span class="special">(</span><span class="identifier">array</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">array</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="identifier">negrightshift</span><span class="special">(),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">greater</span><span class="special">&lt;</span><span class="identifier">DATA_TYPE</span><span class="special">&gt;());</span>
</pre>
<p>
            Examples of functors are:
          </p>
<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">lessthan</span> <span class="special">{</span>
  <span class="keyword">inline</span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">DATA_TYPE</span> <span class="special">&amp;</span><span class="identifier">x</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">DATA_TYPE</span> <span class="special">&amp;</span><span class="identifier">y</span><span class="special">)</span> <span class="keyword">const</span> <span class="special">{</span>
    <span class="keyword">return</span> <span class="identifier">x</span><span class="special">.</span><span class="identifier">a</span> <span class="special">&lt;</span> <span class="identifier">y</span><span class="special">.</span><span class="identifier">a</span><span class="special">;</span>
  <span class="special">}</span>
<span class="special">};</span>
</pre>
<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">bracket</span> <span class="special">{</span>
  <span class="keyword">inline</span> <span class="keyword">unsigned</span> <span class="keyword">char</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">DATA_TYPE</span> <span class="special">&amp;</span><span class="identifier">x</span><span class="special">,</span> <span class="identifier">size_t</span> <span class="identifier">offset</span><span class="special">)</span> <span class="keyword">const</span> <span class="special">{</span>
    <span class="keyword">return</span> <span class="identifier">x</span><span class="special">.</span><span class="identifier">a</span><span class="special">[</span><span class="identifier">offset</span><span class="special">];</span>
  <span class="special">}</span>
<span class="special">};</span>
</pre>
<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">getsize</span> <span class="special">{</span>
  <span class="keyword">inline</span> <span class="identifier">size_t</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">DATA_TYPE</span> <span class="special">&amp;</span><span class="identifier">x</span><span class="special">)</span> <span class="keyword">const</span><span class="special">{</span> <span class="keyword">return</span> <span class="identifier">x</span><span class="special">.</span><span class="identifier">a</span><span class="special">.</span><span class="identifier">size</span><span class="special">();</span> <span class="special">}</span>
<span class="special">};</span>
</pre>
<p>
            and these functors are used thus:
          </p>
<pre class="programlisting"><span class="identifier">string_sort</span><span class="special">(</span><span class="identifier">array</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">array</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="identifier">bracket</span><span class="special">(),</span> <span class="identifier">getsize</span><span class="special">(),</span> <span class="identifier">lessthan</span><span class="special">());</span>
</pre>
<p>
            See <a href="../../../../example/stringfunctorsample.cpp" target="_top">stringfunctorsample.cpp</a>
            for a working example of sorting strings with all functors.
          </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h5 class="title">
<a name="sort.single_thread.spreadsort.overview.performance"></a><a class="link" href="spreadsort.html#sort.single_thread.spreadsort.overview.performance" title="Performance">Performance</a>
</h5></div></div></div>
<p>
            The <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/spreadsort_idm2302.html" title="Function template spreadsort">spreadsort</a></code></code>
            algorithm is a hybrid algorithm; when the number of elements being sorted
            is below a certain number, comparison-based sorting is used. Above it,
            radix sorting is used. The radix-based algorithm will thus cut up the
            problem into small pieces, and either completely sort the data based
            upon its radix if the data is clustered, or finish sorting the cut-down
            pieces with comparison-based sorting.
          </p>
<p>
            The Spreadsort algorithm dynamically chooses either comparison-based
            or radix-based sorting when recursing, whichever provides better worst-case
            performance. This way worst-case performance is guaranteed to be the
            better of <span class="emphasis"><em>𝑶(N⋅log2(N))</em></span> comparisons and <span class="emphasis"><em>𝑶(N⋅log2(K/S
            + S))</em></span> operations where
          </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
                <span class="emphasis"><em>N</em></span> is the number of elements being sorted,
              </li>
<li class="listitem">
                <span class="emphasis"><em>K</em></span> is the length in bits of the key, and
              </li>
<li class="listitem">
                <span class="emphasis"><em>S</em></span> is a constant.
              </li>
</ul></div>
<p>
            This results in substantially improved performance for large <span class="emphasis"><em>N</em></span>;
            <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/integer_sort_idm1895.html" title="Function template integer_sort">integer_sort</a></code></code>
            tends to be 50% to 2X faster than <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>,
            while <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/float_sort_idm1775.html" title="Function template float_sort">float_sort</a></code></code>
            and _string_sort are roughly 2X faster than <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>.
          </p>
<p>
            Performance graphs are provided for <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/integer_sort_idm1895.html" title="Function template integer_sort">integer_sort</a></code></code>,
            <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/float_sort_idm1775.html" title="Function template float_sort">float_sort</a></code></code>,
            and <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/string_sort_idm2523.html" title="Function template string_sort">string_sort</a></code></code>
            in their description.
          </p>
<p>
            Runtime Performance comparisons and graphs were made on a Core 2 Duo
            laptop running Windows Vista 64 with MSVC 8.0, and an old G4 laptop running
            Mac OSX with gcc. <a href="http://www.boost.org/build/doc/html/" target="_top">Boost
            bjam/b2</a> was used to control compilation.
          </p>
<p>
            Direct performance comparisons on a newer x86 system running Ubuntu,
            with the fallback to <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
            at lower input sizes disabled are below.
          </p>
<div class="note"><table border="0" summary="Note">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../../../doc/src/images/note.png"></td>
<th align="left">Note</th>
</tr>
<tr><td align="left" valign="top"><p>
              The fallback to <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
              for smaller input sizes prevents the worse performance seen on the
              left sides of the first two graphs.
            </p></td></tr>
</table></div>
<p>
            <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/integer_sort_idm1895.html" title="Function template integer_sort">integer_sort</a></code></code>
            starts to become faster than <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
            at about 1000 integers (4000 bytes), and <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/string_sort_idm2523.html" title="Function template string_sort">string_sort</a></code></code>
            becomes faster than <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
            at slightly fewer bytes (as few as 30 strings).
          </p>
<div class="note"><table border="0" summary="Note">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../../../doc/src/images/note.png"></td>
<th align="left">Note</th>
</tr>
<tr><td align="left" valign="top"><p>
              The 4-threaded graph has 4 threads doing <span class="bold"><strong>separate
              sorts simultaneously</strong></span> (not splitting up a single sort) as
              a test for thread cache collision and other multi-threaded performance
              issues.
            </p></td></tr>
</table></div>
<p>
            <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/float_sort_idm1775.html" title="Function template float_sort">float_sort</a></code></code>
            times are very similar to <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/integer_sort_idm1895.html" title="Function template integer_sort">integer_sort</a></code></code>
            times.
          </p>
<p>
            <span class="inlinemediaobject"><img src="../../../images/single_threaded.png"></span>
            <span class="inlinemediaobject"><img src="../../../images/4_threaded.png"></span>
            <span class="inlinemediaobject"><img src="../../../images/entropy.png"></span>
            <span class="inlinemediaobject"><img src="../../../images/bits_per_byte.png"></span>
          </p>
<p>
            Histogramming with a fixed maximum number of splits is used because it
            reduces the number of cache misses, thus improving performance relative
            to the approach described in detail in the <a href="http://en.wikipedia.org/wiki/Spreadsort" target="_top">original
            SpreadSort publication</a>.
          </p>
<p>
            The importance of cache-friendly histogramming is described in <a href="http://www.nik.no/2002/Maus.pdf" target="_top">Arne Maus, Adaptive Left Reflex</a>,
            though without the worst-case handling described below.
          </p>
<p>
            The time taken per radix iteration is:
          </p>
<p>
            <span class="emphasis"><em>𝑶(N)</em></span> iterations over the data
          </p>
<p>
            <span class="emphasis"><em>𝑶(N)</em></span> integer-type comparisons (even for _float_sort
            and <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/string_sort_idm2523.html" title="Function template string_sort">string_sort</a></code></code>)
          </p>
<p>
            <span class="emphasis"><em>𝑶(N)</em></span> swaps
          </p>
<p>
            <span class="emphasis"><em>𝑶(2<sup>S</sup>)</em></span> bin operations.
          </p>
<p>
            To obtain <span class="emphasis"><em>𝑶(N)</em></span> worst-case performance per iteration,
            the restriction <span class="emphasis"><em>S &lt;= log2(N)</em></span> is applied, and
            <span class="emphasis"><em>𝑶(2<sup>S</sup>)</em></span> becomes <span class="emphasis"><em>𝑶(N)</em></span>. For each
            such iteration, the number of unsorted bits log2(range) (referred to
            as <span class="emphasis"><em>K</em></span>) per element is reduced by <span class="emphasis"><em>S</em></span>.
            As <span class="emphasis"><em>S</em></span> decreases depending upon the amount of elements
            being sorted, it can drop from a maximum of <span class="emphasis"><em>S<sub>max</sub></em></span>
            to the minimum of <span class="emphasis"><em>S<sub>min</sub></em></span>.
          </p>
<p>
            Assumption: <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
            is assumed to be <span class="emphasis"><em>𝑶(N*log2(N))</em></span>, as <a href="http://en.wikipedia.org/wiki/Introsort" target="_top">introsort</a>
            exists and is commonly used. (If you have a quibble with this please
            take it up with the implementor of your <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>;
            you're welcome to replace the recursive calls to <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
            to calls to <a href="http://en.wikipedia.org/wiki/Introsort" target="_top">introsort</a>
            if your <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
            library call is poorly implemented).
          </p>
<p>
            <a href="http://en.wikipedia.org/wiki/Introsort" target="_top">Introsort</a>
            is not included with this algorithm for simplicity and because the implementor
            of the <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
            call is assumed to know what they're doing.
          </p>
<p>
            To maintain a minimum value for <span class="emphasis"><em>S (S<sub>min</sub>)</em></span>, comparison-based
            sorting has to be used to sort when <span class="emphasis"><em>n &lt;= log2(meanbinsize)</em></span>,
            where <span class="emphasis"><em>log2(meanbinsize) (lbs)</em></span> is a small constant,
            usually between 0 and 4, used to minimize bin overhead per element. There
            is a small corner-case where if <span class="emphasis"><em>K &lt; S<sub>min</sub></em></span> and
            <span class="emphasis"><em>n &gt;= 2^K</em></span>, then the data can be sorted in a single
            radix-based iteration with an <span class="emphasis"><em>S = K</em></span> (this bucketsorting
            special case is by default only applied to <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/float_sort_idm1775.html" title="Function template float_sort">float_sort</a></code></code>).
            So for the final recursion, worst-case performance is:
          </p>
<p>
            1 radix-based iteration if <span class="emphasis"><em>K &lt;= S<sub>min</sub></em></span>,
          </p>
<p>
            or <span class="emphasis"><em>S<sub>min</sub> + lbs</em></span> comparison-based iterations if <span class="emphasis"><em>K
            &gt; S<sub>min</sub></em></span> but <span class="emphasis"><em>n &lt;= 2<sup>(S<sub>min</sub> + lbs)</sup></em></span>.
          </p>
<p>
            So for the final iteration, worst-case runtime is <span class="emphasis"><em>𝑶(N*(S<sub>min</sub> +
            lbs))</em></span> but if <span class="emphasis"><em>K &gt; S<sub>min</sub></em></span> and <span class="emphasis"><em>N
            &gt; 2<sup>(S<sub>min</sub> + lbs)</sup></em></span> then more than 1 radix recursion will be
            required.
          </p>
<p>
            For the second to last iteration, <span class="emphasis"><em>K &lt;= S<sub>min</sub> * 2 + 1</em></span>
            can be handled, (if the data is divided into <span class="emphasis"><em>2<sup>(S<sub>min</sub> + 1)</sup></em></span>
            pieces) or if <span class="emphasis"><em>N &lt; 2<sup>(S<sub>min</sub> + lbs + 1)</sup></em></span>, then it is
            faster to fallback to <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>.
          </p>
<p>
            In the case of a radix-based sort plus recursion, it will take <span class="emphasis"><em>𝑶(N*(S<sub>min</sub> +
            lbs)) + 𝑶(N) = 𝑶(N*(S<sub>min</sub> + lbs + 1))</em></span> worst-case time, as <span class="emphasis"><em>K_remaining
            = K_start - (S<sub>min</sub> + 1)</em></span>, and <span class="emphasis"><em>K_start &lt;= S<sub>min</sub> * 2
            + 1</em></span>.
          </p>
<p>
            Alternatively, comparison-based sorting is used if <span class="emphasis"><em>N &lt; 2<sup>(S<sub>min</sub> +
            lbs + 1)</sup></em></span>, which will take <span class="emphasis"><em>𝑶(N*(S<sub>min</sub> + lbs + 1))</em></span>
            time.
          </p>
<p>
            So either way <span class="emphasis"><em>𝑶(N*(S<sub>min</sub> + lbs + 1))</em></span> is the worst-case
            time for the second to last iteration, which occurs if <span class="emphasis"><em>K &lt;=
            S<sub>min</sub> * 2 + </em></span>1 or <span class="emphasis"><em>N &lt; 2<sup>(S<sub>min</sub> + lbs + 1)</sup></em></span>.
          </p>
<p>
            This continues as long as <span class="emphasis"><em>S<sub>min</sub> &lt;= S &lt;= S<sub>max</sub></em></span>,
            so that for <span class="emphasis"><em>K_m &lt;= K_(m-1) + S<sub>min</sub> + m</em></span> where <span class="emphasis"><em>m</em></span>
            is the maximum number of iterations after this one has finished, or where
            <span class="emphasis"><em>N &lt; 2<sup>(S<sub>min</sub> + lbs + m)</sup></em></span>, then the worst-case runtime
            is <span class="emphasis"><em>𝑶(N*(S<sub>min</sub> + lbs + m))</em></span>.
          </p>
<p>
               <span class="emphasis"><em>K_m</em></span> at <span class="emphasis"><em>m &lt;= (S<sub>max</sub> - S<sub>min</sub>)</em></span>
            works out to:
          </p>
<p>
               <span class="emphasis"><em>K_1 &lt;= (S<sub>min</sub>) + S<sub>min</sub> + 1 &lt;= 2S<sub>min</sub> + 1</em></span>
          </p>
<p>
               <span class="emphasis"><em>K_2 &lt;= (2S<sub>min</sub> + 1) + S<sub>min</sub> + 2</em></span>
          </p>
<p>
            as the sum from 0 to <span class="emphasis"><em>m</em></span> is <span class="emphasis"><em>m(m + 1)/2</em></span>
          </p>
<p>
               <span class="emphasis"><em>K_m &lt;= (m + 1)S<sub>min</sub> + m(m + 1)/2 &lt;= (S<sub>min</sub> + m/2)(m + 1)</em></span>
          </p>
<p>
            substituting in S<sub>max</sub> - S<sub>min</sub> for m
          </p>
<p>
               <span class="emphasis"><em>K_(S<sub>max</sub> - S<sub>min</sub>) &lt;= (S<sub>min</sub> + (S<sub>max</sub> - S<sub>min</sub>)/2)*(S<sub>max</sub> - S<sub>min</sub> + 1)</em></span>
          </p>
<p>
               <span class="emphasis"><em>K_(S<sub>max</sub> - S<sub>min</sub>) &lt;= (S<sub>min</sub> + S<sub>max</sub>) * (S<sub>max</sub> - S<sub>min</sub> + 1)/2</em></span>
          </p>
<p>
            Since this involves <span class="emphasis"><em>S<sub>max</sub> - S<sub>min</sub> + 1</em></span> iterations, this
            works out to dividing <span class="emphasis"><em>K</em></span> into an average <span class="emphasis"><em>(S<sub>min</sub> +
            S<sub>max</sub>)</em></span>/2 pieces per iteration.
          </p>
<p>
            To finish the problem from this point takes <span class="emphasis"><em>𝑶(N * (S<sub>max</sub> - S<sub>min</sub>))</em></span>
            for <span class="emphasis"><em>m</em></span> iterations, plus the worst-case of <span class="emphasis"><em>𝑶(N*(S<sub>min</sub> +
            lbs))</em></span> for the last iteration, for a total of <span class="emphasis"><em>𝑶(N
            *(S<sub>max</sub> + lbs))</em></span> time.
          </p>
<p>
            When <span class="emphasis"><em>m &gt; S<sub>max</sub> - S<sub>min</sub></em></span>, the problem is divided into
            <span class="emphasis"><em>S<sub>max</sub></em></span> pieces per iteration, or <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
            is called if <span class="emphasis"><em>N &lt; 2^(m + S<sub>min</sub> + lbs)</em></span>. For this
            range:
          </p>
<p>
               <span class="emphasis"><em>K_m &lt;= K_(m - 1) + S<sub>max</sub></em></span>, providing runtime of
          </p>
<p>
               <span class="emphasis"><em>𝑶(N *((K - K_(S<sub>max</sub> - S<sub>min</sub>))/S<sub>max</sub> + S<sub>max</sub> + lbs))</em></span> if recursive,
          </p>
<p>
            or <span class="emphasis"><em>𝑶(N * log(2^(m + S<sub>min</sub> + lbs)))</em></span> if comparison-based,
          </p>
<p>
            which simplifies to <span class="emphasis"><em>𝑶(N * (m + S<sub>min</sub> + lbs))</em></span>, which
            substitutes to <span class="emphasis"><em>𝑶(N * ((m - (S<sub>max</sub> - S<sub>min</sub>)) + S<sub>max</sub> + lbs))</em></span>,
            which given that <span class="emphasis"><em>m - (S<sub>max</sub> - S<sub>min</sub>) &lt;= (K - K_(S<sub>max</sub> - S<sub>min</sub>))/S<sub>max</sub></em></span>
            (otherwise a lesser number of radix-based iterations would be used)
          </p>
<p>
            also comes out to <span class="emphasis"><em>𝑶(N *((K - K_(S<sub>max</sub> - S<sub>min</sub>))/S<sub>max</sub> + S<sub>max</sub> + lbs))</em></span>.
          </p>
<p>
            Asymptotically, for large <span class="emphasis"><em>N</em></span> and large <span class="emphasis"><em>K</em></span>,
            this simplifies to:
          </p>
<p>
               <span class="emphasis"><em>𝑶(N * (K/S<sub>max</sub> + S<sub>max</sub> + lbs))</em></span>,
          </p>
<p>
            simplifying out the constants related to the <span class="emphasis"><em>S<sub>max</sub> - S<sub>min</sub></em></span>
            range, providing an additional <span class="emphasis"><em>𝑶(N * (S<sub>max</sub> + lbs))</em></span>
            runtime on top of the <span class="emphasis"><em>𝑶(N * (K/S))</em></span> performance of
            LSD <a href="http://en.wikipedia.org/wiki/Radix_sort" target="_top">radix sort</a>,
            but without the <span class="emphasis"><em>𝑶(N)</em></span> memory overhead. For simplicity,
            because <span class="emphasis"><em>lbs</em></span> is a small constant (0 can be used,
            and performs reasonably), it is ignored when summarizing the performance
            in further discussions. By checking whether comparison-based sorting
            is better, Spreadsort is also <span class="emphasis"><em>𝑶(N*log(N))</em></span>, whichever
            is better, and unlike LSD <a href="http://en.wikipedia.org/wiki/Radix_sort" target="_top">radix
            sort</a>, can perform much better than the worst-case if the data
            is either evenly distributed or highly clustered.
          </p>
<p>
            This analysis was for <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/integer_sort_idm1895.html" title="Function template integer_sort">integer_sort</a></code></code>
            and <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/float_sort_idm1775.html" title="Function template float_sort">float_sort</a></code></code>.
            <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/string_sort_idm2523.html" title="Function template string_sort">string_sort</a></code></code>
            differs in that <span class="emphasis"><em>S<sub>min</sub> = S<sub>max</sub> = sizeof(Char_type) * 8</em></span>,
            <span class="emphasis"><em>lbs</em></span> is 0, and that <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>'s
            comparison is not a constant-time operation, so strictly speaking <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/string_sort_idm2523.html" title="Function template string_sort">string_sort</a></code></code>
            runtime is
          </p>
<p>
               <span class="emphasis"><em>𝑶(N * (K/S<sub>max</sub> + (S<sub>max</sub> comparisons)))</em></span>.
          </p>
<p>
            Worst-case, this ends up being <span class="emphasis"><em>𝑶(N * K)</em></span> (where <span class="emphasis"><em>K</em></span>
            is the mean string length in bytes), as described for <a href="http://en.wikipedia.org/wiki/American_flag_sort" target="_top">American
            flag sort</a>, which is better than the
          </p>
<p>
               <span class="emphasis"><em>𝑶(N * K * log(N))</em></span>
          </p>
<p>
            worst-case for comparison-based sorting.
          </p>
</div>
<div class="section">
<div class="titlepage"><div><div><h5 class="title">
<a name="sort.single_thread.spreadsort.overview.tuning"></a><a class="link" href="spreadsort.html#sort.single_thread.spreadsort.overview.tuning" title="Tuning">Tuning</a>
</h5></div></div></div>
<p>
            <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/integer_sort_idm1895.html" title="Function template integer_sort">integer_sort</a></code></code>
            and <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/float_sort_idm1775.html" title="Function template float_sort">float_sort</a></code></code>
            have tuning constants that control how the radix-sorting portion of those
            algorithms work. The ideal constant values for <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/integer_sort_idm1895.html" title="Function template integer_sort">integer_sort</a></code></code>
            and <code class="literal"><code class="computeroutput"><a class="link" href="../../boost/sort/spreadsort/float_sort_idm1775.html" title="Function template float_sort">float_sort</a></code></code>
            vary depending on the platform, compiler, and data being sorted. By far
            the most important constant is <span class="emphasis"><em>max_splits</em></span>, which
            defines how many pieces the radix-sorting portion splits the data into
            per iteration.
          </p>
<p>
            The ideal value of <span class="emphasis"><em>max_splits</em></span> depends upon the size
            of the L1 processor cache, and is between 10 and 13 on many systems.
            A default value of 11 is used. For mostly-sorted data, a much larger
            value is better, as swaps (and thus cache misses) are rare, but this
            hurts runtime severely for unsorted data, so is not recommended.
          </p>
<p>
            On some x86 systems, when the total number of elements being sorted is
            small ( less than 1 million or so), the ideal <span class="emphasis"><em>max_splits</em></span>
            can be substantially larger, such as 17. This is suspected to be because
            all the data fits into the L2 cache, and misses from L1 cache to L2 cache
            do not impact performance as severely as misses to main memory. Modifying
            tuning constants other than <span class="emphasis"><em>max_splits</em></span> is not recommended,
            as the performance improvement for changing other constants is usually
            minor.
          </p>
<p>
            If you can afford to let it run for a day, and have at least 1GB of free
            memory, the perl command: <code class="computeroutput">./tune.pl -large -tune</code> (UNIX)
            or <code class="computeroutput">perl tune.pl -large -tune -windows</code> (Windows) can be used
            to automatically tune these constants. This should be run from the <code class="computeroutput">libs/sort
            directory</code> inside the boost home directory. This will work to identify
            the <code class="computeroutput">ideal constants.hpp</code> settings for your system, testing
            on various distributions in a 20 million element (80MB) file, and additionally
            verifies that all sorting routines sort correctly across various data
            distributions. Alternatively, you can test with the file size you're
            most concerned with <code class="computeroutput">./tune.pl number -tune</code> (UNIX) or <code class="computeroutput">perl
            tune.pl number -tune -windows</code> (Windows). Substitute the number
            of elements you want to test with for <code class="computeroutput">number</code>. Otherwise,
            just use the options it comes with, they're decent. With default settings
            <code class="computeroutput">./tune.pl -tune</code> (UNIX) <code class="computeroutput">perl tune.pl -tune -windows</code>
            (Windows), the script will take hours to run (less than a day), but may
            not pick the correct <span class="emphasis"><em>max_splits</em></span> if it is over 10.
            Alternatively, you can add the <code class="computeroutput">-small</code> option to make it
            take just a few minutes, tuning for smaller vector sizes (one hundred
            thousand elements), but the resulting constants may not be good for large
            files (see above note about <span class="emphasis"><em>max_splits</em></span> on Windows).
          </p>
<p>
            The tuning script can also be used just to verify that sorting works
            correctly on your system, and see how much of a speedup it gets, by omiting
            the "-tune" option. This runs at the end of tuning runs. Default
            args will take about an hour to run and give accurate results on decent-sized
            test vectors. <code class="computeroutput">./tune.pl -small</code> (UNIX) <code class="computeroutput">perl tune.pl
            -small -windows</code> (Windows) is a faster option, that tests on smaller
            vectors and isn't as accurate.
          </p>
<p>
            If any differences are encountered during tuning, please call <code class="computeroutput">tune.pl</code>
            with <code class="computeroutput">-debug &gt; log_file_name</code>. If the resulting log file
            contains compilation or permissions issues, it is likely an issue with
            your setup. If some other type of error is encountered (or result differences),
            please send them to the library author at spreadsort@gmail.com. Including
            the zipped <code class="computeroutput">input.txt</code> that was being used is also helpful.
          </p>
</div>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2014-2017 Steven
      Ross, Francisco Tapia, Orson Peters<p>
        Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost
        Software License, Version 1.0</a>.
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="../single_thread.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../single_thread.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="spreadsort/sort_hpp.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
